<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  <base data-ice="baseUrl" href="../../../">
  <title data-ice="title">src/internal/tree.js | jstreemap Library</title>
  <link type="text/css" rel="stylesheet" href="css/style.css">
  <link type="text/css" rel="stylesheet" href="css/prettify-tomorrow.css">
  <script src="script/prettify/prettify.js"></script>
  <script src="script/manual.js"></script>
<meta name="description" content="Associative containers (sets, maps) library for JavaScript, using red-black trees."><meta property="twitter:card" content="summary"><meta property="twitter:title" content="jstreemap Library"><meta property="twitter:description" content="Associative containers (sets, maps) library for JavaScript, using red-black trees."></head>
<body class="layout-container" data-ice="rootContainer">

<header>
  <a href="./">Home</a>
  
  <a href="identifiers.html">Reference</a>
  <a href="source.html">Source</a>
  
  <div class="search-box">
  <span>
    <img src="./image/search.png">
    <span class="search-input-edge"></span><input class="search-input"><span class="search-input-edge"></span>
  </span>
    <ul class="search-result"></ul>
  </div>
<a style="position:relative; top:3px;" href="https://github.com/Kirusi/jstreemap"><img width="20px" src="./image/github.png"></a></header>

<nav class="navigation" data-ice="nav"><div>
  <ul>
    
  <li data-ice="doc"><a data-ice="dirPath" class="nav-dir-path" href="identifiers.html#public">public</a><span data-ice="kind" class="kind-class">C</span><span data-ice="name"><span><a href="class/src/public/insertion-result.js~InsertionResult.html">InsertionResult</a></span></span></li>
<li data-ice="doc"><span data-ice="kind" class="kind-class">C</span><span data-ice="name"><span><a href="class/src/public/iterators.js~BaseIterator.html">BaseIterator</a></span></span></li>
<li data-ice="doc"><span data-ice="kind" class="kind-class">C</span><span data-ice="name"><span><a href="class/src/public/iterators.js~Iterator.html">Iterator</a></span></span></li>
<li data-ice="doc"><span data-ice="kind" class="kind-class">C</span><span data-ice="name"><span><a href="class/src/public/iterators.js~ReverseIterator.html">ReverseIterator</a></span></span></li>
<li data-ice="doc"><span data-ice="kind" class="kind-class">C</span><span data-ice="name"><span><a href="class/src/public/js-iterators.js~JsIterator.html">JsIterator</a></span></span></li>
<li data-ice="doc"><span data-ice="kind" class="kind-class">C</span><span data-ice="name"><span><a href="class/src/public/js-iterators.js~JsReverseIterator.html">JsReverseIterator</a></span></span></li>
<li data-ice="doc"><span data-ice="kind" class="kind-class">C</span><span data-ice="name"><span><a href="class/src/public/tree-map.js~TreeMap.html">TreeMap</a></span></span></li>
<li data-ice="doc"><span data-ice="kind" class="kind-class">C</span><span data-ice="name"><span><a href="class/src/public/tree-multimap.js~TreeMultiMap.html">TreeMultiMap</a></span></span></li>
<li data-ice="doc"><span data-ice="kind" class="kind-class">C</span><span data-ice="name"><span><a href="class/src/public/tree-multiset.js~TreeMultiSet.html">TreeMultiSet</a></span></span></li>
<li data-ice="doc"><span data-ice="kind" class="kind-class">C</span><span data-ice="name"><span><a href="class/src/public/tree-set.js~TreeSet.html">TreeSet</a></span></span></li>
</ul>
</div>
</nav>

<div class="content" data-ice="content"><h1 data-ice="title">src/internal/tree.js</h1>
<pre class="source-code line-number raw-source-code"><code class="prettyprint linenums" data-ice="content">&apos;use strict&apos;;

/** @ignore */
const {TreeNode, RED, BLACK} = require(&apos;./tree-node&apos;);
/** @ignore */
const {JsIterator, JsReverseIterator} = require(&apos;../public/js-iterators&apos;);
/** @ignore */
const {Iterator, ReverseIterator} = require(&apos;../public/iterators&apos;);
/** @ignore */
const {KeyOnlyPolicy, ValueOnlyPolicy, KeyValuePolicy} = require(&apos;./policies&apos;);
/** @ignore */
const {InsertionResult} = require(&apos;../public/insertion-result&apos;);

/** insertion mode of a multimap, nodes with the same keys can be added */
const INSERT_MULTI = 1;
/** if a node with the same key already exists then the subsequent attempts are ignored */
const INSERT_UNIQUE = 2;
/** if a node with the same key already exists then it&apos;s value is replaced on subsequent attempts */
const INSERT_REPLACE = 3;

/**
 * @private
 * Special node in a tree is created for performance reasons
 */
class Head {
    /** default constructor */
    constructor() {
        /** node with the smallest key */
        this.leftmost = this;
        /** node with the largest key */
        this.rightmost = this;
        /** root node of the tree */
        this.root = this;
        /** number of nodes in the tree */
        this.size = 0;
        /** extra tag used in debuggin of unit tests */
        this.id = &apos;HEAD&apos;;
    }
}

/**
 * @private
 * 3-way comparison, similar to strcmp and memcp in C programming language
 * @returns +1 if the value of rhs is greater than lhs
 *          -1 if the value of rhs is less than lhs
 *           0 if values are the same
 */
function compare(lhs, rhs) {
    if (lhs &lt; rhs) {
        return -1;
    }
    else if (lhs === rhs) {
        return 0;
    }
    else {
        return 1;
    }
}

/**
 * Red-black tree
 * @access private
 */
class Tree {
    /** default constructor of an empty tree */
    constructor() {
        /** head */
        this.head = new Head();
        /** 3-way comparison function */
        this.compare = compare;
        /** must be an instance of KeyOnlyPolicy for sets, or KeyValuePolicy for maps */
        this.valuePolicy = new KeyOnlyPolicy();
    }

    /**
     * Deletes all nodes in the tree
     */
    clear() {
        this.head = new Head();
    }

    /**
     * @returns number of nodes in the tree
     */
    size() {
        return this.head.size;
    }

    /**
     * @private
     * A wrapper that calls 3-way comparison of node keys
     * @param {*} lhs
     * @param {*} rhs
     */
    compareNodes(lhs, rhs) {
        return this.compare(lhs.key, rhs.key);
    }

    /**
     * @private
     * used by rotation operations
     */
    replaceNode(oldNode, newNode) {
        if (oldNode === newNode) {
            return;
        }
        if (oldNode.parent === null) {
            this.head.root = newNode;
        }
        else {
            if (oldNode === oldNode.parent.left) {
                oldNode.parent.left = newNode;
            }
            else {
                oldNode.parent.right = newNode;
            }
        }

        if (!this.isLeaf(newNode)) {
            newNode.parent = oldNode.parent;
        }
    }

    /**
     * Rebalances tree as described below

              X                                           Y
             / \                                         / \
            Y   c         right rotate --&gt;              a   X
           / \            &lt;--  left rotate                 / \
          a   b                                           b   c
     * @private
     */
    rotateLeft(node) {
        let right = node.right;
        if (this.isLeaf(right)) {
            throw new Error(&apos;rotateLeft can\&apos;t be performed. The tree is corrupted&apos;);
        }
        this.replaceNode(node, right);

        node.right = right.left;
        if (right.left !== null) {
            right.left.parent = node;
        }

        right.left = node;
        node.parent = right;
    }

    /**
     * Rebalances tree as described in rotateLeft
     * @param {*} node - parent node
     */
    rotateRight(node) {
        let left = node.left;
        if (this.isLeaf(left)) {
            throw new Error(&apos;rotateRight can\&apos;t be performed. The tree is corrupted&apos;);
        }
        this.replaceNode(node, left);

        node.left = left.right;
        if (left.right !== null) {
            left.right.parent = node;
        }

        left.right = node;
        node.parent = left;
    }

    /**
     * @returns true - for null pointers and head node; false - for all other nodes
     * @param {*} node
     */
    isLeaf(node) {
        if (node === null || node === this.head) {
            return true;
        }
        return false;
    }

    /**
     * Leaf nodes are considered &apos;black&apos;. All real nodes contain &apos;color&apos; data member
     * @param {*} node
     */
    fetchColor(node) {
        if (this.isLeaf(node)) {
            return BLACK;
        }
        else {
            return node.color;
        }
    }

    /**
     * Tests a node for &apos;blackness&apos;.
     * @param {*} node
     */
    isBlack(node) {
        return (this.fetchColor(node) === BLACK);
    }

    /**
     * Tests node for &apos;redness&apos;.
     * @param {*} node
     */
    isRed(node) {
        return (this.fetchColor(node) === RED);
    }

    /* ===========================
       INSERT
       =========================== */
    /**
     * A node will be inserted into the tree even if nodes with the same key already exist
     * @param {*} node
     * @returns {InsertionResult} - indicates whether a node was added and provides iterator to it.
     */
    insertMulti(node) {
        return this.insertNode(node, INSERT_MULTI);
    }

    /**
     * The node is inserted into the tree only if nodes with the same key do not exist there
     * @param {*} node
     * @returns {InsertionResult} - indicates whether a node was added and provides iterator to it.
     */
    insertUnique(node) {
        return this.insertNode(node, INSERT_UNIQUE);
    }

    /**
     * The node is inserted. If a node with the same key exists it&apos;s value will be replaced by the value of the new node
     * @param {*} node
     * @returns {InsertionResult} - indicates whether a node was added and provides iterator to it.
     */
    insertOrReplace(node) {
        return this.insertNode(node, INSERT_REPLACE);
    }

    /**
     * @private
     * Inserts node. Updates head node. Rebalances tree.
     * @param {*} n - node
     * @param {*} mode - one of INSERT_MULTI, INSERT_UNIQUE, INSERT_REPLACE
     * @returns {InsertionResult} - indicates whether a node was added and provides iterator to it.
     */
    insertNode(n, mode = INSERT_MULTI) {
        let res = this.insertNodeInternal(this.head.root, n, mode);
        if (res.wasAdded) {
            if (this.head.size === 0) {
                this.head.root = n;
                this.head.leftmost = n;
                this.head.rightmost = n;

                n.left = this.head;
                n.right = this.head;
            }
            else if (this.head.leftmost.left === n) {
                this.head.leftmost = n;
                n.left = this.head;
            }
            else if (this.head.rightmost.right === n) {
                this.head.rightmost = n;
                n.right = this.head;
            }
            this.insertRepairTree(n);
            this.head.size = this.head.size + 1;
        }
        return res;
    }

    /**
     * @private
     * Inserts node according to the mode
     * @param {*} root - root node of the tree
     * @param {*} n - node to be inserted
     * @param {*} mode - one of INSERT_MULTI, INSERT_UNIQUE, INSERT_REPLACE
     * @returns {InsertionResult} - indicates whether a node was added and provides iterator to it.
     */
    insertNodeInternal(root, n, mode) {
        // recursively descend the tree until a leaf is found
        let x = root;
        let y = null;
        let rc = -1;
        // find matching node
        while (!this.isLeaf(x)) {
            y = x;
            rc = this.compareNodes(n, y);
            if (rc &lt; 0) {
                x = y.left;
            }
            else if (rc &gt; 0) {
                x = y.right;
            }
            else {
                // node with the same key value
                switch (mode) {
                    case INSERT_UNIQUE:
                        // it&apos;s a duplicate
                        return new InsertionResult(false, false, undefined);
                    case INSERT_REPLACE:
                        this.valuePolicy.copy(y, n);
                        return new InsertionResult(false, true, new Iterator(y, this));
                    default:
                        // INSERT_MULTI
                        x = y.right;
                }
            }
        }
        if (this.isLeaf(y)) {
            n.parent = null;
            n.left = this.head;
            n.right = this.head;
        }
        else {
            n.parent = y;
            if (rc &lt; 0) {
                y.left = n;
            }
            else {
                y.right = n;
            }
        }
        return new InsertionResult(true, false, new Iterator(n, this));
    }

    /**
     * @private
     * The method is decribed at: https://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Insertion
     * @param {*} n - node
     */
    insertRepairTree(n) {
        if (n.parent === null) {
            this.repairCase1(n);
        }
        else if (this.isBlack(n.parent)) {
        /* insert_case2(n);
           // do nothing */
        }
        else if (this.isRed(n.uncle())) {
            this.repairCase3(n);
        }
        else {
            this.repairCase4(n);
        }
    }

    /**
     * @private
     * The method is decribed at: https://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Insertion
     * @param {*} n - node
     */
    repairCase1(n) {
        n.color = BLACK;
    }

    /**
     * @private
     * The method is decribed at: https://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Insertion
     * @param {*} n - node
     */
    repairCase3(n) {
        n.parent.color = BLACK;
        n.uncle().color = BLACK;
        n.grandparent().color = RED;
        this.insertRepairTree(n.grandparent());
    }

    /**
     * @private
     * The method is decribed at: https://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Insertion
     * @param {*} n - node
     */
    repairCase4(n) {
        let p = n.parent;
        let g = n.grandparent();

        let nr = null;
        if ((g.left !== null)
            &amp;&amp; (n === g.left.right)) {
            this.rotateLeft(p);
            n = n.left;
        }
        else if ((g.right !== null)
            &amp;&amp; (n === g.right.left)) {
            this.rotateRight(p);
            n = n.right;
        }

        p = n.parent;
        g = n.grandparent();
        if (n === p.left) {
            this.rotateRight(g);
        }
        else {
            this.rotateLeft(g);
        }

        p.color = BLACK;
        g.color = RED;
    }

    /**
     * @returns the node with the highest key for the subtree of the specified root node
     * @param {*} node - root node of the subtree to be evaluated
     */
    fetchMaximum(node) {
        while (!this.isLeaf(node.right)) {
            node = node.right;
        }

        return node;
    }

    /**
     * @returns the node with the lowest key for the subtree of the specified root node
     * @param {*} node - root node of the subtree to be evaluated
     */
    fetchMinimum(node) {
        while (!this.isLeaf(node.left)) {
            node = node.left;
        }

        return node;
    }

    /* ===========================
       ERASE
       =========================== */
    /**
     * Removes node from the tree
     * @param {*} node
     */
    erase(node) {
        if (this.isLeaf(node)) {
            return;
        }

        this.eraseInternal(node);
        let h = this.head;
        h.size = h.size - 1;
    }

    /**
     * @private
     * The method is decribed at: https://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Removal
     * @param {*} node - node
     */
    eraseInternal(node) {
        if (!this.isLeaf(node.left)
            &amp;&amp; !this.isLeaf(node.right)) {
            let pred = this.fetchMaximum(node.left);

            this.valuePolicy.copy(node, pred);
            node = pred;
        }

        let child = (this.isLeaf(node.right)) ? node.left : node.right;

        if (this.isBlack(node)) {
            this.eraseCase1(node);
        }
        this.replaceNode(node, child);
        if (this.head.size === 2) {
            if (!this.isLeaf(child)) {
                // Root node must be BLACK
                child.color = BLACK;
            }
        }

        let h = this.head;
        if (this.isLeaf(child)) {
            /* The node didn&apos;t have children and it was removed
               the head needs to update leftmost, rightmost pointers */
            if (h.leftmost === node) {
                let p = node.parent;
                if (p !== null) {
                    h.leftmost = p;
                    p.left = h;
                }
                else {
                    h.leftmost = h;
                }
            }
            if (h.rightmost === node) {
                let p = node.parent;
                if (p !== null) {
                    h.rightmost = p;
                    p.right = h;
                }
                else {
                    h.rightmost = h;
                }
            }
        }
        else {
            // the node had a child. Now node is removed. Any references should point to the child now
            if (h.leftmost === node) {
                h.leftmost = child;
                child.left = h;
            }
            if (h.rightmost === node) {
                h.rightmost = child;
                child.right = h;
            }
        }
    }

    /**
     * @private
     * The method is decribed at: https://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Removal
     * @param {*} node
     */
    eraseCase1(node) {
        if (node.parent === null) {
            return;
        }
        else {
            this.eraseCase2(node);
        }
    }

    /**
     * @private
     * The method is decribed at: https://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Removal
     * @param {*} node
     */
    eraseCase2(node) {
        let s = node.sibling();

        if (this.isRed(s)) {
            node.parent.color = RED;
            s.color = BLACK;

            if (node === node.parent.left) {
                this.rotateLeft(node.parent);
            }
            else {
                this.rotateRight(node.parent);
            }
        }
        this.eraseCase3(node);
    }

    /**
     * @private
     * The method is decribed at: https://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Removal
     * @param {*} node
     */
    eraseCase3(node) {
        let s = node.sibling();
        let p = node.parent;
        if (this.isBlack(p)
            &amp;&amp; this.isBlack(s)
            &amp;&amp; this.isBlack(s.left)
            &amp;&amp; this.isBlack(s.right)) {

            s.color = RED;
            this.eraseCase1(p);
        }
        else {
            this.eraseCase4(node);
        }
    }

    /**
     * @private
     * The method is decribed at: https://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Removal
     * @param {*} node
     */
    eraseCase4(node) {
        let s = node.sibling();
        let p = node.parent;
        if (this.isRed(p)
            &amp;&amp; this.isBlack(s)
            &amp;&amp; this.isBlack(s.left)
            &amp;&amp; this.isBlack(s.right)) {

            s.color = RED;
            p.color = BLACK;
        }
        else {
            this.eraseCase5(node);
        }
    }

    /**
     * @private
     * The method is decribed at: https://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Removal
     * @param {*} node
     */
    eraseCase5(node) {
        let s = node.sibling();
        let p = node.parent;
        /* The check below is unnecessary
           due to case 2 (even though case 2 changed the sibling to a sibling&apos;s child,
           the sibling&apos;s child can&apos;t be red, since no red parent can have a red child). */
        /* if ((!this.isLeaf(s))
               &amp;&amp; this.isBlack(s)) { */

        /* the following statements just force the red to be on the left of the left of the parent,
           or right of the right, so case six will rotate correctly. */
        if (node === p.left
            &amp;&amp; this.isRed(s.left)
			&amp;&amp; this.isBlack(s.right)) {

            s.color = RED;
            s.left.color = BLACK;
            this.rotateRight(s);
        }
        else if (node === p.right
            &amp;&amp; this.isBlack(s.left)
            &amp;&amp; this.isRed(s.right)) {

            s.color = RED;
            s.right.color = BLACK;
            this.rotateLeft(s);
        }
        //}
        this.eraseCase6(node);
    }

    /**
     * @private
     * The method is decribed at: https://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Removal
     * @param {*} node
     */
    eraseCase6(node) {
        let s = node.sibling();
        let p = node.parent;
        s.color = this.fetchColor(p);
        p.color = BLACK;

        if (node === p.left) {
            s.right.color = BLACK;
            this.rotateLeft(p);
        }
        else {
            s.left.color = BLACK;
            this.rotateRight(p);
        }
    }

    /* ===========================
       SEARCH BY KEY
       =========================== */
    /**
    * @returns an iterator pointin to a node with matching key value. If node is not found then end() iterator is returned.
    * @param {*} k - key value
    */
    find(k) {
        let y = this.head;
        let x = y.root;
        while (!this.isLeaf(x)) {
            let rc = this.compare(x.key, k);
            if (rc &gt; 0) {
                y = x;
                x = x.left;
            }
            else if (rc &lt; 0) {
                y = x;
                x = x.right;
            }
            else {
                return new Iterator(x, this);
            }
        }
        return new Iterator(this.head, this);
    }

    /**
     * @returns an iterator pointing to the first node in the tree that is not less than
     * (i.e. greater or equal to) the specified key value, or end() if no such node is found.
     * @param {*} k - key value
     */
    lowerBound(k) {
        let y = this.head;
        let x = y.root;
        while (!this.isLeaf(x)) {
            let rc = this.compare(x.key, k);
            if (rc &gt;= 0) {
                y = x;
                x = x.left;
            }
            else {
                x = x.right;
            }
        }
        return new Iterator(y, this);
    }

    /**
     * @returns an iterator pointing to the first node in the tree that is greater than
     * the specified key value, or end() if no such node is found.
     * @param {*} k - key value
     */
    upperBound(k) {
        let y = this.head;
        let x = y.root;
        while (!this.isLeaf(x)) {
            let rc = this.compare(x.key, k);
            if (rc &gt; 0) {
                y = x;
                x = x.left;
            }
            else {
                x = x.right;
            }
        }
        return new Iterator(y, this);
    }

    /* ===========================
       ITERATORS
       =========================== */

    /**
     * @returns iterator pointing to the node with the lowest key
     */
    begin() {
        return new Iterator(this.head.leftmost, this);
    }

    /**
     * @returns iterator pointing to the node following the node with the highest key
     */
    end() {
        return new Iterator(this.head, this);
    }

    /**
     * @returns iterator pointing to the node with the highest key
     */
    rbegin() {
        return new ReverseIterator(this.head.rightmost, this);
    }

    /**
     * @returns iterator pointing to the node preceding the node with the lowest key
     */
    rend() {
        return new ReverseIterator(this.head, this);
    }

    /**
     * @private
     * provides support for ES6 forward iteration
     */
    jsBegin() {
        return this.head.leftmost;
    }

    /**
     * @private
     * provides support for ES6 forward iteration
     */
    jsEnd() {
        return this.head;
    }

    /**
     * @private
     * provides support for ES6 reverse iteration
     */
    jsRbegin() {
        return this.head.rightmost;
    }

    /**
     * @private
     * provides support for ES6 forward iteration
     */
    jsRend() {
        return this.head;
    }

    /**
     * @returns node following the specified node in ascending order of their keys
     * @param {*} n - node
     */
    next(n) {
        if (n === this.head) {
            return this.head.leftmost;
        }
        if (n.right === this.head) {
            return this.head;
        }
        if (n.right !== null) {
            let res = this.fetchMinimum(n.right);
            return res;
        }
        else {
            while (n.parent.left !== n) {
                n = n.parent;
            }
            return n.parent;
        }
    }

    /**
     * @returns node preceding the specified node in ascending order of their keys
     * @param {*} n - node
     */
    prev(n) {
        if (n === this.head) {
            return this.head.rightmost;
        }
        if (n.left === this.head) {
            return this.head;
        }
        if (n.left !== null) {
            let res = this.fetchMaximum(n.left);
            return res;
        }
        else {
            while (n.parent.right !== n) {
                n = n.parent;
            }
            return n.parent;
        }
    }

    /**
     * ES6 forward iteration
     */
    [Symbol.iterator]() {
        return new JsIterator(this);
    }

    /**
     * ES6 reverse iteration
     */
    backward() {
        return new JsReverseIterator(this);
    }

    /**
     * @returns a new JsIterator object that contains the [key, value] pairs for each element in the order of the keys.
     */
    entries() {
        return new JsIterator(this);
    }

    /**
     * @returns a new JsIterator object that contains the keys for each element in the order of the keys.
     */
    keys() {
        return new JsIterator(this, new KeyOnlyPolicy());
    }

    /**
     * @returns a new JsIterator object that contains the values for each element in the order of the keys.
     */
    values() {
        return new JsIterator(this, new ValueOnlyPolicy());
    }

    /**
     * @returns first element of the container, or undefined if container is empty
     */
    first() {
        if (this.size() === 0) {
            return undefined;
        }
        else {
            let it = this.begin();
            return this.valuePolicy.fetch(it.node);
        }
    }

    /**
     * @returns last element of the container, or undefined if container is empty
     */
    last() {
        if (this.size() === 0) {
            return undefined;
        }
        else {
            let it = this.rbegin();
            return this.valuePolicy.fetch(it.node);
        }
    }

    /**
     * @returns String representation of the container
     */
    toString() {
        let parts = [];
        for (let it = this.begin(); !it.equals(this.end()); it.next()) {
            // convert each key-value pair
            parts.push(this.valuePolicy.toString(it.node));
        }
        return &apos;{&apos; + parts.join(&apos;,&apos;) + &apos;}&apos;;
    }

    /**
     * @returns String tag of this class
     */
    get [Symbol.toStringTag]() {
        return &apos;Tree&apos;;
    }

    /**
     * @returns constructor object for this class
     */
    static get [Symbol.species]() {
        return Tree;
    }

}

module.exports = {
    Tree: Tree,
    compare: compare
};
</code></pre>

</div>

<footer class="footer">
  Generated by <a href="https://esdoc.org">ESDoc<span data-ice="esdocVersion">(1.0.4)</span><img src="./image/esdoc-logo-mini-black.png"></a>
</footer>

<script src="script/search_index.js"></script>
<script src="script/search.js"></script>
<script src="script/pretty-print.js"></script>
<script src="script/inherited-summary.js"></script>
<script src="script/test-summary.js"></script>
<script src="script/inner-link.js"></script>
<script src="script/patch-for-local.js"></script>
</body>
</html>
